\documentclass[12pt,a4paper]{article}
\usepackage{xeCJK}
\usepackage{ctex}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{abstract}
\usepackage{float}
\usepackage{algorithmicx}
\usepackage[ruled]{algorithm}
\usepackage{algpseudocode}
\usepackage{xcolor}
\usepackage{setspace}
\usepackage{color}
\usepackage{bm}
\usepackage{url}
\usepackage{cite}
\usepackage{array}
\usepackage{textcomp}
\usepackage{appendix}
\usepackage{listings}

\setstretch{1.2} 
\setlength{\parindent}{0.8cm}
\geometry{left=3cm,right=3cm,top=2.5cm,bottom=2.5cm}

\title{\vspace{-2cm} \textbf{第十三次课堂作业}}

\author{邵柯欣 \\学号：3200103310 \\课程名称：数据科学的数学基础}

\date{\today}

\begin{document}
\maketitle
\section{8.1}
解：根据Lliyd算法编写matlab如下，
\begin{verbatim}
P=load('P.csv'); %对数据集Q，改为P=load('Q.csv');
g = zeros(120,1);
k = 3; %改变k的值，多次运行观察结果
r=round(rand(1,k)*120);
S = zeros(k,6);
for i = 1:k
    S(i,:) = P(r(i),:);
end
for n = 1:5000
    Xi = zeros(k,1);
    sXi = zeros(k,6);
    for i = 1:120
        d = ones(1,k);
        for j = 1:k
            d(j) = norm(S(j,:)-P(i,:),2);
        end
        [a,b] = min(d);
        g(i,1) = b;
        Xi(b) = Xi(b) + 1;
        sXi(b,:) = sXi(b,:) + P(i,:);
    end
    for i = 1:k
        S(i,:) = sXi(i,:)/Xi(i);
    end
end
\end{verbatim}
改变k的值后，多次运行，观察每次结果的变化。

对于数据集P，当$k <= 3$时，结果基本稳定;当$k > 3$时，结果变化较大。因此，P中有3个集类。

对于数据集Q，当$k <= 4$时，结果基本稳定;当$k > 4$时，结果变化较大。因此，Q中有4个集类。
\section{8.8}
解：根据Lliyd算法编写matlab如下，
\begin{verbatim}
Ck=load('Ck.csv');
g = zeros(1040,1);
k = 3;
r=round(rand(1,k)*120);
S = zeros(k,2);
S(1,:) = Ck(1,:);
for l = 2:k
    for i = 1:1040
        d = ones(1,l-1);
        for j = 1:l-1
            d(j) = norm(S(j,:)-Ck(i,:),2);
        end
        [a,b] = min(d);
        g(i,1) = b;
    end
    s_d = zeros(l-1,1);
    s = zeros(l-1,2);
    for i = 1:1040
        if norm(S(g(i),:)-Ck(i)) > s_d(g(i))
            s_d(g(i)) = norm(S(g(i),:));
            s(g(i),:) = Ck(i);
        end
    end
    S(l,:) = min(s);
    
end
for i = 1:1040
    d = ones(1,3);
    for j = 1:3
        d(j) = norm(S(j,:)-Ck(i,:),2);
    end
    [a,b] = min(d);
    g(i) = b;
end
\end{verbatim}
得到结果$S = [s1,s2,s3]^T$是数据集的三个中心，
\begin{verbatim}
S = 
-4.4357 -5.6060
 4.0319  4.0319
-4.4357 -4.4357
\end{verbatim}

\section{给定6个数据点的集合$X = {(1,3), (2,-1), (2,2), (-1,-1), (-2,0), (3,-1)}$,$S = {s1,s2,s3}$满足$minimize \quad max_{x \in X}\| \phi_S(x) - x\|_1$,$S^*$为最优解,证明$minimize \quad max_{x \in X}\| \phi_{S^*}(x) - x\|_1$}
证明：\\
运用$Gonzalez$算法，求得一组$\hat{S} = {(1,3),(2,-1),(-1,-1)}$。
$$max_{x \in X}d(\phi_{\hat{S}}(x),x) = 5$$
$$\because \quad max_{x \in X}d(\phi_{\hat{S}}(x),x) <= 2*max_{x \in X}d(\phi_{S*}(x),x)$$
$$\therefore \quad max_{x \in X}d(\phi_{S*}(x),x) >= \dfrac{5}{2} >= 1$$
\end{document}
